package xin.javashare.sort;

/**
 * 程序清单24.2 【冒泡排序】算法复杂度O(n^2),最佳情况O(n),只遍历一次
 * 加入needNextPass只是在一次遍历没有交换元素时停止遍历，
 * 但若能记住一次遍历最后交换的位置，那么此位置后的元素已经排好序，不需再比较交换。
 * 若向两端进行双向冒泡，则更能减少遍历次数
 */
public class BubbleSort {
    public static void bubbleSort(int[] list) {
        if (list == null || list.length < 2) return;
        boolean needNextPass = true;
        for (int k = 1; k < list.length && needNextPass; k++) {
            needNextPass = false;
            for (int i = 0; i < list.length - k; i++) {
                if (list[i] > list[i + 1]) {
                    int temp = list[i];
                    list[i] = list[i + 1];
                    list[i + 1] = temp;
                    needNextPass = true;
                }
            }
        }
    }


    // 标记交换位置
    public static void bubbleSort2(int[] list) {
        if (list == null || list.length < 2) return;
        int i = list.length - 1;// 初始时，最后的位置保持不变
        while (i > 0) {
            int pos = 0;//每次遍历开始时无交换记录
            for (int j = 0; j < i; j++) {
                if (list[j] > list[j + 1]) {
                    pos = j;//记录交换的位置
                    int temp = list[j];
                    list[j] = list[j + 1];
                    list[j + 1] = temp;
                }
            }
            i = pos;//下一次遍历的范围
        }

    }

    // 双向遍历
    public static void bubbleSort3(int[] arr) {
        if (arr == null || arr.length < 2) return;
        int low = 0;
        int high = arr.length - 1;
        int temp = 0;
        int j = 0;
        while (low < high) {
            // 正向冒泡，找到最大值
            for (j = low; j < high; ++j ) {
                if (arr[j] > arr[j + 1]) {
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
            --high;
            // 反向冒泡，找到最小值
            for (j = high; j > low; --j) {
                if (arr[j] < arr[j - 1]) {
                    temp = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = temp;
                }
            }
            ++low;
        }
    }

    // 双向遍历+标记交换位置
    public static void bubbleSort4(int[] arr) {
        if (arr == null || arr.length < 2) return;
        int low = 0;
        int high = arr.length - 1;
        int temp = 0;
        int j = 0;
        while (low < high) {
            int lowPos = 0;
            int highPos = 0;
            // 正向冒泡，找到最大值
            for (j = low; j < high; ++j ) {
                if (arr[j] > arr[j + 1]) {
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    highPos = j;
                }
            }
            high = highPos;

            // 反向冒泡，找到最小值
            for (j = high; j > low; --j) {
                if (arr[j] < arr[j - 1]) {
                    lowPos = j;
                    temp = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = temp;
                }
            }
            low = lowPos;
        }
    }

    public static void main(String[] args) {
        int[] list = {2, 3, 2, 5, 6, 1, -2, 3, 14, 12};
        bubbleSort4(list);
        for (int i = 0; i < list.length; i++) {
            System.out.print(list[i] + " ");
        }
    }

}
